Abstract: The Team Orienteering Problem with Time Windows (TOPTW)
deals with deriving a number of tours comprising a subset of candidate
nodes (each associated with a \prot" value and a visiting time window)
so as to maximize the overall \prot", while respecting a specied time
span. TOPTW has been used as a reference model for the Tourist Trip
Design Problem (TTDP) in order to derive near-optimal multiple-day
tours for tourists visiting a destination featuring several points of inter-
est (POIs), taking into account a multitude of POI attributes. TOPTW
is an NP-hard problem and the most ecient known heuristic is based on
IteratedLocalSearch (ILS). However, ILS treats each POI separately;
hence it tends to overlook highly protable areas of POIs situated far
from the current location, considering them too time-expensive to visit.
We propose two cluster-based extensions to ILS addressing the afore-
mentioned weakness by grouping POIs on disjoint clusters (based on
geographical criteria), thereby making visits to such POIs more attrac-
tive. Our approaches improve on ILS with respect to solutions quality,
while executing at comparable time and reducing the frequency of overly
long transfers among POIs.